[AGC005D]K Perm Counting

2020-02-17
#动态规划Dp #容斥
Atcoder

题意

求所有n阶排列中，满足$\forall |i-a_i|\not=k$的排列数

题解

转变为容斥问题，可以发现题目等价于二分图

现在要解决的就是二分图匹大小为$k$的方案数

猛然发现二分图由一些链构成，那么每条链分开来Dp，最后再卷积合并即可

插播，可以不Dp，就是$C_{i-j}^{j}$，把j个点先取出来再接回去​

$ans=\sum_{i=0}^{n} (-1)^{i}\cdot g(i)\cdot (n-i)!​$

FFT什么的就懒得写了

调试记录

算ans的时候没加mo导致爆负

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#define int long long
const int maxn = 2005;
const int mo = 924844033;
using namespace std;
int f[maxn][maxn][2], g[2][maxn], n, k;
int fac[maxn];
signed main(){
	scanf("%lld%lld", &n, &k); fac[0] = 1;
	for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % mo;
	f[1][0][0] = 1;
	for (int i = 1; i <= n / k; i++){
		for (int j = 0; j <= i / 2; j++){
			f[i + 1][j][0] = (f[i][j][1] + f[i][j][0]) % mo;
			f[i + 1][j + 1][1] = f[i][j][0];
		}
	} g[0][0] = 1; int cnt = 0;
//	printf("%d\n", (f[n / k + 1][5][0] + f[n / k + 1][5][1]));
	int T = 0;
	for (int s = 1; s <= k; s++){
		int len = (n - s) / k + 1;
		for (int i = 0; i <= cnt; i++)
			for (int j = 0; j <= len / 2; j++)
				g[T ^ 1][i + j] = (g[T ^ 1][i + j] + 1ll * g[T][i] * (f[len][j][0] + f[len][j][1]) % mo) % mo;
		for (int i = 0; i <= cnt; i++) g[T][i] = 0; T ^= 1;
		cnt += len / 2;
		for (int i = 0; i <= cnt; i++)
			for (int j = 0; j <= len / 2; j++)
				g[T ^ 1][i + j] = (g[T ^ 1][i + j] + 1ll * g[T][i] * (f[len][j][0] + f[len][j][1]) % mo) % mo;
		for (int i = 0; i <= cnt; i++) g[T][i] = 0; T ^= 1;
		cnt += len / 2;
	}
	int ans = 0;
	for (int i = 0; i <= n; i++)
		ans = (ans + mo + ((i & 1) ? -1 : 1) * 1ll * g[T][i] % mo * fac[n - i] % mo) % mo;
	printf("%lld\n", ans);
	return 0;
}